The present invention relates to input capture in general and in particular to interactively generating vector representations of a drawing.
Input capture involves the conversion of user inputs into a computer-readable form, typically involving a user input device electronically coupled to a processor that executes software instructions or other processing to generate the computer-readable and stored representation of what the user intended to input. Where the input is text, a keyboard might be used and the user intent is often easy to determine, based on the keys pressed and the order pressed. However, where the user input is drawing elements, such as lines, curves, and other drawing expressions, it can be more difficult to generate the stored representation that accurately reflects the user's intended input.
Of course, digital input capture can be set at a very high resolution, such as capturing location of an electronic pen very frequently, along with pressure, rotation, etc. to capture exactly what movements the user made, to the resolution of some small quantization and sampling error, but even that might not be what the user intended and that might not be usable for many purposes. For example, if the samples are just points at which locations are measured, there may be too many points to work with and the points might be disjoint and at some resolution provide a very disjointed input.
Such problems are well known and there have been some proposed solutions, such as to have a processor evaluate the sampled user inputs from an input device and attempt to generate vector representations based on the user's inputs after the user is done drawing. Digital curve capture has become an important means of computer input in recent years as tablets and stylus-based devices have become more pervasive. The conversion of user input into digital curves and the use of those digital curves have a wide range of applications, including drawing, painting, gesturing, signature capture, motion capture. While curve capture is often described with reference to capture of curves drawn on a two-dimensional surface, curve capture can also be captured as input in three dimensions (or four, if the time dimension is considered).
Digital input devices including computer mice, stylus-based tablets, 3D spatial trackers and touch screens supply discrete samples as the user draws a continuous path. It may be the case that the samples comprise pen location, tilt (e.g., pen angle of attack relative to the “paper” of the input device), pen rotation (relevant when the pen tip is not symmetrical), pressure and possibly other sample components. In many examples, the samples are taken at a regular interval and that is the example used herein, but samples might be taken at irregular intervals. For example, a sample might be taken every 0.10 seconds or every 0.5 seconds regardless of activity, or might be taken at a variable rate that depends on user activity or user specification of a sample rate.
In any case, when samples are taken, they can be stored as raw data, but many applications find the data more useful if it is processed to generate curve/intent data indicating the curves that the user likely intended. Simply connecting the sampled points with linear segments is often not an acceptable solution, such as when the discontinuous result does not represent the continuous path intended by the user. Therefore, what is often desired is a smooth, continuous curve that fits to the input samples in such a way that the curve attempts to reproduce the intended path of the user's drawing.
There are known processes for producing such curves, and digital drawing applications such as the Adobe Photoshop™ program, the Adobe Illustrator™ program, the Inkscape™ program, the Autodesk Sketchbook Pro™ program, Toonboom Harmony™ and the like, employ such a process, in order to avoid producing unpleasant linear segments. The stored output of such processes is sometimes referred to as “vector artwork” to distinguish from the sampled dots of the input data.
Vector artwork is a popular choice for digital art creation due to its resolution-independent nature. The input curves are explicitly stored, allowing the final drawing to be scaled to various resolutions without loss of quality. This permits high-quality viewing on a variety of differently sized devices. There is a large body of work related to generating a smooth or “fair” curve to a sequence of input samples. Most of these approaches, however, do not address the problem of dealing with a sequence of input samples that is being appended in real-time. One typical standard solution is for a processor to generate linear segments between the input samples as the user draws, possibly displaying those to the user on a display device as the user draws, and then generate a smooth curve to the samples once the user finishes the current stroke and display that smooth curve. This has the implication that when the user lifts the pen after creating a stroke, the processor will visually change what is displayed, but the computed curve might no longer represent what the artist intended and require the artist user to recreate a long input sequence.
Most state-of-the-art algorithms require a complete set of static input samples in order to produce a result. This is primarily due to the complexity of algorithms that cannot be easily applied interactively every time a new sample is recorded. The recent work of [Baran] outlines an algorithm that produces curves comprised of clothoid splines. However, the processing time needed to produce a result is limiting in that it cannot be applied in real-time.
Some approaches may generate a curve as the samples are recorded. These approaches fit parametric curves (e.g., cubic Beziers), one at a time, while the user draws. Every time a new input sample is obtained and added to the raw data, the processor computes an updated current Bezier curve such that the updated current Bezier curve fits a range of recent samples. Once the fitting error passes a defined threshold, the current Bezier curve is frozen and a new Bezier curve is created with its starting point and tangent now fixed in order to connect smoothly to the previous. The resulting final curve is a smooth piece-wise C1 Bezier curve. Curves may be fit by reducing the squared distance of the current Bezier curve to the piecewise linear segments between input samples, as opposed to the distance of the input samples to the current Bezier curve. This is an optimization allowing the algorithm to be interactive but comes at the cost of potentially misrepresenting the input if samples are far apart.